package com.wzh.arithmetic.sort;

import java.util.Arrays;

/**
 * @Author zh wang
 * @Create 2025/4/16 19:58
 */
public class SortUtil {
    /**
     * 冒泡排序（Bubble Sort）
     * 算法逻辑：
     * 1. 依次比较相邻元素，前大后小则交换
     * 2. 每轮遍历将最大值冒泡到末尾
     * 3. 重复n-1轮完成排序
     * @param arr
     */
    public static void sort01(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * ### 选择排序（Selection Sort）
     *
     * **算法逻辑**：
     *
     * 1. 在未排序序列中找到最小元素
     * 2. 与序列起始位置元素交换
     * 3. 重复上述过程直到排序完成
     * @param arr
     */
    public static void sort02(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = minIndex + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * ### 插入排序（Insertion Sort）
     *
     * **算法逻辑**：
     *
     * 1. 将第一个元素视为已排序序列
     * 2. 取出下一个元素，在已排序序列中从后向前扫描
     * 3. 找到相应位置插入元素
     * 4. 重复步骤2-3
     * @param arr
     */
    public static void sort03(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int temp;
        for (int i=1; i < arr.length; i++) {
            for (int j=i-1; j>=0; j--) {
                if (arr[j] <= arr[i]) {
                    if (j + 1 != i) {
                        temp = arr[i];
                        arr[i] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    }

    /**
     * ### 希尔排序（Shell Sort）
     *
     * **算法逻辑**：
     *
     * 1. 定义增量序列（本文使用gap/2）
     * 2. 按增量分组进行插入排序
     * 3. 逐步缩小增量直至1
     * @param arr
     */
    public static void sort04(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int temp;
    }

    public static void main(String[] args) {
        int length = 10;
        // 随机数组
        int[] arr = getRandomArray(length);
        System.out.println("排序前："+Arrays.toString(arr));
        sort03(arr);
        System.out.println("排序后："+Arrays.toString(arr));
        // 检查结果
        System.out.println("结果：" + isSorted(1000, length));
    }

    private static String isSorted(int n, int length) {
        // 自动测试n次
        for (int i = 0; i < n; i++) {
            int[] arr = getRandomArray(length);
            // 复制数组
            int[] arr2 = Arrays.copyOf(arr, arr.length);
            sort01(arr);
            if (!isSorted(arr)) {
                System.out.println("失败原数组："+Arrays.toString(arr2));
                System.out.println("失败排序后："+Arrays.toString(arr));
                return "失败";
            }
        }
        return "成功";
    }
    private static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    private static int[] getRandomArray(int i) {
        // 随机数组
        int[] arr = new int[i];
        for (int j = 0; j < i; j++) {
            arr[j] = (int) (Math.random() * 100);
        }
        return arr;
    }

}
